/* 插入排序 基本思路就是将一个记录插入到已经有序的的序列中，
 从而得到新的有序序列长度 +1 
 先来个简单粗暴的理解
 */

function insert(arr = []) {
    const rs = [arr.pop()];
    while (arr.length) {
        const el = arr.pop();
        if (rs[rs.length - 1] <= el) {
            rs.push(el)
            continue
        }
        for (let i = 0; i < rs.length; i++) {
            if (rs[i] > el) {
        // 这里的res已经是个递增序列了 遇到比自己小的肯定放前面      
                rs.splice(i, 0, el)
                break;// 找到自己的位置了 结束
            }
        }

    }
    return rs
}



// 不使用额外的数组 实现splice的插入
function insert2(arr) {
    for (let i = 1; i < arr.length; i++) {
        // 这样要先记住第i个元素
        let t = arr[i]
        // 内循环倒着 遍历有序的部分
        for (let j = i - 1; j >= 0; j--) {
            // 这里不使用splice就有点像冒泡排序了，不过前面的部分已经有序 只需先记住 最后一个 实现整体后移，不需要挨个交换
            if (t < arr[j]) {// 小 t就要往前移 对应元素后移
                arr[j + 1] = arr[j]
            } else { //大就放后面 
                arr[j + 1] = t
                break; //找到位置了 结束
            }
        }
        // 走过了这个循环并且 这个值比第一个还小 那么还需要补上一个判断
        if(arr[0] > t){
            arr[0] = t
        }
    }
}


function getRandArr(n) {
    const arr = []
    for (let i = 0; i < n; i++) {

        arr.push(Math.random() * 2 * n | 0);
    }
    return arr

}

const arr1 = getRandArr(10);
console.log('%c', 'color:green', arr1);

let arr2 = insert([...arr1]);
console.log('%c排序后', 'color:red', arr2);
insert2(arr1)
console.log('%c排序后', 'color:red', arr1);
//




